437. Path Sum III
Medium

Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values along the path equals targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

 

Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3

 

Constraints:

  • The number of nodes in the tree is in the range [0, 1000].
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000
Accepted
276,138
Submissions
568,268
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions

Average Rating: 4.92 (159 votes)

Premium

Solution


Prefix Sum: What is it

In this article, we're going to discuss simple but powerful prefix sum technique: one pass + linear time complexity.

Prefix sum is a sum of the current value with all previous elements starting from the beginning of the structure.

It could be defined for 1D arrays (sum the current value with all the previous integers),

append Figure 1. Prefix sum for 1D array.

for 2D arrays (sum of the current value with the integers above or on the left)

append Figure 2. Prefix sum for 2D array.

or for the binary trees (sum the values of the current node
and all parent nodes),

append Figure 3. Prefix sum for the binary tree.




Prefix Sum: How to Use: Number of Continuous Subarrays that Sum to Target

You might want to use the prefix sum technique for the problems like "Find a number of continuous subarrays/submatrices/tree paths that sum to target".

Before going to the current problem with the tree, let's check the idea on a simpler example Find a number of continuous subarrays that sum to target.

  • Use a variable to track the current prefix sum and a hashmap "prefix sum -> how many times was it seen so far".

append Figure 4. Find a number of continuous subarrays that sum to target.

  • Parse the input structure and count the requested subarrays/submatrices/tree paths along the way with the help of that hashmap. How to count?

There could be two situations. In situation 1, the subarray with the target sum starts from the beginning of the array. That means that the current prefix sum is equal to the target sum, and we increase the counter by 1.

append Figure 5. Situation 1: The subarray starts from the beginning of the array.

In situation 2, the subarray with the target sum starts somewhere in the middle. That means we should add to the counter the number of times we have seen the prefix sum curr_sum - target so far: count += h[curr_sum - target].

The logic is simple: the current prefix sum is curr_sum, and some elements before the prefix sum was curr_sum - target. All the elements in between sum up to curr_sum - (curr_sum - target) = target.

append Figure 6. Situation 2: The subarray starts somewhere in the middle.

Solution for Number of Continuous Subarrays that Sum to Target

Here is an implementation of the solution for Find a number of continuous subarrays that sum to target.




Approach 1: Prefix Sum

Now let's reuse the same algorithm and the same code for the case of the binary tree.

There is just one thing that is particular for the binary tree. There are two ways to go forward - to the left and to the right. To keep parent->child direction, we shouldn't blend prefix sums from the left and right subtrees in one hashmap.

Algorithm

  • Let's initialize tree paths counter count = 0, and the hashmap h "prefix sum -> how many times was it seen so far".

  • One could parse the tree using recursive preorder traversal: node -> left -> right: preorder(node: TreeNode, curr_sum: int) -> None. This function takes two arguments: a tree node and a prefix sum before that node. To start the recursion chain, one should call preorder(root, 0).

    • The first thing is to update the current prefix sum by adding the value of the current node: curr_sum += node.val.

    • Now one could update the counter. One should consider two situations.

      In situation 1, the tree path with the target sum starts from the root. That means the current prefix sum is equal to the target sum curr_sum == k, so one should increase the counter by 1: count += 1.

      In situation 2, the tree path with the target sum starts somewhere downwards. That means we should add to the counter the number of times we have seen the prefix sum curr_sum - target so far: count += h[curr_sum - target].

      The logic is simple: the current prefix sum is curr_sum, and several elements before the prefix sum was curr_sum - target. All the elements in between sum up to curr_sum - (curr_sum - target) = target.

    • Now it's time to update the hashmap: h[curr_sum] += 1.

    • Let's parse left and right subtrees: preorder(node.left, curr_sum), preorder(node.right, curr_sum).

    • Now the current subtree is processed. It's time to remove the current prefix sum from the hashmap, in order not to blend the parallel subtrees: h[curr_sum] -= 1.

  • Now the preorder traversal is done, and the counter is updated. Return it.

append Figure 7. Situation 1 vs situation 2.

Implementation

On the following example the target sum is equal to 8.

Current
1 / 17

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N), where NN is a number of nodes. During preorder traversal, each node is visited once.

  • Space complexity: up to O(N)\mathcal{O}(N) to keep the hashmap of prefix sums, where NN is a number of nodes.

Report Article Issue

Comments: 40
vishruthkhare3's avatar
Read More

This is the best editorial i've ever seen. Very well elaborated and correlated with other pre-existing problems.

96
Reply
Share
Report
jxy530's avatar
Read More

I took me a while to appreciate this solution, especially the part "currSum - k".

19
Reply
Share
Report
thepatriot's avatar
Read More

beautiful article, thank you

26
Reply
Share
Report
sainimkar's avatar
Read More

How is this a medium question?!

7
Show 4 replies
Reply
Share
Report
daiyun's avatar
Read More

Took me a little while to think through why h[curr_sum] += 1 has to come after count += h[curr_sum - k]. Think about an edge case when sum equals to 0.

7
Show 1 reply
Reply
Share
Report
eastbridgeb3's avatar
Read More

Why do we use globals in leetcode, my understanding was globals are not liked by interviewers.

7
Show 3 replies
Reply
Share
Report
jingjing_334's avatar
Read More

Thanks for the write-up. I learned a lot!!

3
Reply
Share
Report
kentwongg's avatar
Read More

nice write up...learned a lot!

Can someone confirm something?

            # remove the current sum from the hashmap
            # in order not to use it during 
            # the parallel subtree processing
            h[curr_sum] -= 1

when the code bottoms out (reaches an end leaf/node) on the recursive calls, the two preorder calls return nothing, then it proceeds to h[curr_sum] -= 1 when then removes that node value from the hashmap, correct?

2
Show 3 replies
Reply
Share
Report
ringo123's avatar
Read More

Great explanation; very much enjoying reading it! Thank you.

2
Reply
Share
Report
elulcao's avatar
Read More

Pretty well explained, I just refactored a little bit the code to make it more similar to other solutions I have in Leetcode. On the other hand, the prefix Sum is the way I prefer to tackle this problem.

2
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
08/08/2020 12:54Accepted24 ms15.6 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.